#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

//方法1，有点超时
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int size = nums.size();
        vector<int> dp(size,0); //访问到的标为1
        dp[0] = 1;
        for(int i = 0;i<size;++i){
            if(dp[i]!=0){
                if((nums[i]+i)>=(size-1)){
                    return true;
                }
                for(int j = 0;j<=nums[i];++j){
                    if((i+j)<size){
                        dp[i+j] = 1;
                        
                    }
                }
            }
            
        }
        return false;

        
    }
};


//方法2，设置dp[i]为数组中前i个能走出的最远距离
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxvalue = nums[0];
        int size = nums.size();
        for(int i=0;i<=maxvalue;++i){
            if(maxvalue>=size-1){
                return true;
            }
            maxvalue = max(maxvalue,i+nums[i]);
        }
        return false;
    }
};



int main(){
    Solution S;
    vector<int> nums = {3,2,1,0,4};
    cout<<S.canJump(nums)<<endl;
}